#include "heap.h"

void HeapInit(Heap* php)
{
  assert(php);

  php->a = NULL;
  php->size = php->capacity =0;
}

void HeapDestroy(Heap* php)
{
  assert(php);

  free(php->a);
  php->a = NULL;
  php->capacity = php->size =0;
}

void Swap(HeapDateType* child, HeapDateType* parent){
  HeapDateType tmp = *child;
  *child=  *parent;
  *parent = tmp;
}

void AdjustUp(HeapDateType* a,int child){
  int parent = (child-1)/2;
  while(child > 0){
    if(a[child] < a[parent]){
      Swap(&a[child],&a[parent]);
      child = parent;
      parent = (child-1)/2;
    }else{
      break;
    }
}

}


void HeapPush(Heap* php,HeapDateType x)
{
  assert(php);
  
  if(php->size == php->capacity){
  int newCapacity = php->capacity == 0?4:php->capacity*2;
  HeapDateType* tmp = (HeapDateType*)realloc(php->a,sizeof(HeapDateType)*newCapacity);

  if(tmp == NULL){
    perror("realloc fail\n");
  }

  php->a = tmp;
  php->capacity = newCapacity;
  }

  php->a[php->size] = x;
  php->size++;

  AdjustUp(php->a,php->size-1);
}

void HeapPrint(Heap* php)
{
  assert(php);

  for(size_t i =0; i<php->size; i++){
    std::cout << php->a[i] << " ";
  }
  std::cout << std::endl;
}

void AdjustDown(HeapDateType* a,int n, int parent)
{
  int child = parent*2+1;
  while(child < n){
    if(child+1 < n && a[child+1] < a[child]){
      child++;
    }

    if(a[child] < a[parent]){
      Swap(&a[child],&a[parent]);
      parent = child;
      child = parent*2+1;
    }else{
      break;
    }
  }
}

HeapDateType HeapTop(Heap* php)
{
  assert(php);
  assert(php->size > 0);

  return php->a[0];
}

void HeapPop(Heap* php)
{
  assert(php);
  assert(php->size > 0);

  Swap(&php->a[0],&php->a[php->size-1]);
  --php->size;

  AdjustDown(php->a,php->size,0);

  
}

bool HeapEmpty(Heap* php)
{
 assert(php);

 return php->size == 0;
}
